/*
 * Quadtree.cpp
 *
 *  Created on: 2009/01/22
 *      Author: Yongshik Cho
 */

#include "Quadtree.h"
#include "RenderDevice.h"
#include "Exception.h"


const float Quadtree::_DEFAULT_MIN_QUAD_WIDTH 		= 2.f;
const float Quadtree::_DEFAULT_MIN_QUAD_HEIGHT		= 2.f;


Quadtree::Quadtree(Quadtree* parent, const Vector2D& p1, const Vector2D& p2)
{
	mParent = parent;
	mLeftTop = 0;
	mRightTop = 0;
	mLeftBottom = 0;
	mRightBottom = 0;

	mRect = new Rect2D(p1, p2);
	if(!mRect)
		AltoThrow(Exception::ERR_MEMORY);
}

Quadtree::Quadtree(Quadtree* parent, const Rect2D& rect)
{
	// TODO Auto-generated constructor stub
	mParent = parent;
	mLeftTop = 0;
	mRightTop = 0;
	mLeftBottom = 0;
	mRightBottom = 0;

	mRect = new Rect2D(rect);
	if(!mRect)
		AltoThrow(Exception::ERR_MEMORY);
}

Quadtree::~Quadtree()
{
	// TODO Auto-generated destructor stub
	//delete rect
	SAFE_DELETE(mRect);

	//delete Quadtree
	SAFE_DELETE(mLeftTop);
	SAFE_DELETE(mRightTop);
	SAFE_DELETE(mLeftBottom);
	SAFE_DELETE(mRightBottom);

	//clear renderables
	for(QuadtreeType::iterator it=mRenderables.begin();it!=mRenderables.end();++it)
	{
		RenderableType* rt = (*it).second;
		if(rt)
		{
			rt->clear();
			SAFE_DELETE(rt);
		}
	}

	mRenderables.clear();
}

const bool Quadtree::addRenderable(Renderable* r)
{
	if(!r || !r->getParent())
		return false;

	Vector2D hp = Vector2D(mRect->getWidth()/2.f, mRect->getHeight()/2.f);
	if(hp.x < _DEFAULT_MIN_QUAD_WIDTH && hp.y < _DEFAULT_MIN_QUAD_HEIGHT)
		return false;

	if(mRect->isPointIn(r->getViewRect()))
	{
		bool added = false;
		if(!mLeftTop && !added)
		{
			mLeftTop = new Quadtree(this, Vector2D(0.f, 0.f), hp);
			added = mLeftTop->addRenderable(r);
		}
		if(!mRightTop && !added)
		{
			mRightTop = new Quadtree(this, Vector2D(hp.x, 0.f), hp);
			added = mRightTop->addRenderable(r);
		}
		if(!mLeftBottom && !added)
		{
			mLeftBottom = new Quadtree(this, Vector2D(0.f, hp.y), hp);
			added = mLeftBottom->addRenderable(r);
		}
		if(!mRightBottom && !added)
		{
			mRightBottom = new Quadtree(this, Vector2D(hp.x, hp.y), hp);
			added = mRightBottom->addRenderable(r);
		}

		if(!added)
		{
			if(!mRenderables[this])
			{
				mRenderables[this] = new RenderableType;
			}
			mRenderables[this]->push_back(r);
			return true;
		}
	}

	return false;
}

void Quadtree::subRenderable(Renderable* r)
{
	for(QuadtreeType::iterator it=mRenderables.begin();it!=mRenderables.end();++it)
	{
		RenderableType* rt = (*it).second;
		if(rt)
		{
			RenderableType::iterator idx = std::find(rt->begin(), rt->end(), r);
			if(idx != rt->end())
			{
				rt->erase(idx);
				break;
			}
		}
	}
}

Quadtree* Quadtree::getQuadtree(Renderable* r)
{
	for(QuadtreeType::iterator it=mRenderables.begin();it!=mRenderables.end();++it)
	{
		RenderableType* rt = (*it).second;
		if(rt)
		{
			if(std::find(rt->begin(), rt->end(), r) != rt->end())
				return (*it).first;
		}
	}

	return 0;
}

Rect2D* Quadtree::getRect(Renderable* r)
{
	Quadtree* q = getQuadtree(r);
	if(q)
		return q->mRect;

	return 0;
}

const uint32 Quadtree::getRenderableCount()
{
	uint32 count = 0;
	for(QuadtreeType::iterator it=mRenderables.begin();it!=mRenderables.end();++it)
	{
		Quadtree* q = (*it).first;
		RenderableType* rt = (*it).second;
		if(rt)
		{
			count += (uint32)rt->size();
		}

		if(q)
			count += q->getRenderableCount();
	}

	return count;
}

void Quadtree::clear()
{
	//clear renderables
	for(QuadtreeType::iterator it=mRenderables.begin();it!=mRenderables.end();++it)
	{
		RenderableType* rt = (*it).second;
		if(rt)
		{
			rt->clear();
		}
	}

	if(mLeftTop)
		mLeftTop->clear();

	if(mRightTop)
		mRightTop->clear();

	if(mLeftBottom)
		mLeftBottom->clear();

	if(mRightBottom)
		mRightBottom->clear();
}
